#define  _CRT_SECURE_NO_WARNINGS 1
#include"head.h"

//青蛙跳台问题
//有一只青蛙
// 一次可以条跳1个台阶		剩余n-1个台阶，这n-1个台阶有Jump(n-1)种跳法
// 一次可以条跳2个台阶		剩余n-2个台阶，这n-2个台阶有Jump(n-2)种跳法
// 
// Jump(n) = 跳到第n个台阶总共有几种跳法
// 
// Jump(n) = Jump(n-1) + Jump(n-2)
// 
// 
// 
// n = 1  
//  1
// n = 2
//  1+1  2
// n = 3
//  1+1+1  1+2  2+1  
// n = 4
//  1+1+1+1  1+1+2  1+2+1  2+1+1  2+2
// 
// 青蛙跳上一级台阶之后，做为新起点
// 假设一共有4级
// 先跳一级，剩3级，3级有3种跳法
// 先跳两级，剩2级，2级有2种跳法
// Jump(4) = Jump(3) + Jump(2)
// 
// 动态规划：用上一步的结果，来快速计算得到下一步的结果
//

int Jump(int n)
{
	if (n <= 0)
		return 0;
	if (n == 1)
		return 1;
	if (n == 2)
		return 2;
	int *dp = new int[n + 1];
	dp[1] = 1;
	dp[2] = 2;
	for (int i = 3; i <= n; i++)
	{
		dp[i] = dp[i - 1] + dp[i - 2];
	}
	int ret = dp[n];
	delete[] dp;
	return ret;
}